// 给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。
// 按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
// "123"
// "132"
// "213"
// "231"
// "312"
// "321"


// 方法一、深度优先搜索+回溯算法破解
function getPermutation(n: number, k: number) {
    const res: string[] = []; // 结果数组
    const path: string = ''; // 当前路径
    const hasSelected: boolean[] = new Array(n).fill(false);
    getPermutation_DFS(n, k, res, path, hasSelected);
    return res[res.length - 1];
};

function getPermutation_DFS(n: number, k: number, res: string[], path: string, hasSelected: boolean[]) {
    if (k === res.length) { // 递归出口1
        return;
    }
    if (path.length === n) { // 递归出口2
        res.push(path);
        return;
    }
    for (let i = 0; i < n; i++) {
        // 如果当前的结果数组还没有被选中
        if (!hasSelected[i]) {
            hasSelected[i] = true;
            path = path + (n + 1);
            getPermutation_DFS(n, k, res, path, hasSelected);
            // 回溯算法部分
            hasSelected[i] = false;
            path = path.slice(0, -1);
        }
    }
};


// 方法二：深度优先搜索+剪枝方法
function getPermutation2(n: number, k: number): string {
    const path: string = ''; // 当前路径
    const hasSelected: boolean[] = new Array(n).fill(false);
    const facArray: number[] = getPermutation2_getFac(n);
    return getPermutation2_DFS(n, k, 0, path, hasSelected, facArray);
};

/**
 * @param depth 表示当前深度优先搜索所处深度的位置
 * @param path 表示当前的路径
 * @param facArray 表示对应1-n对应的阶乘数组(从1开始)
 */

function getPermutation2_DFS(n: number, k: number, depth: number, path: string,
    hasSelected: boolean[], facArray: number[]): string {
    if (depth === n) { // 递归出口1 深度已经走到了结果的长度
        return path;
    }
    console.log(k);
    let currDepthCount: number = facArray[n - depth - 1]; // 表示当前深度该分支的计算个数
    for (let i = 1; i <= n; i++) {
        if (!hasSelected[i]) { // 若当前数字未被选中
            // 剪枝条件1，如果当前计算个数小于k，说明即便加上了整个分支也达不到k，即这个分支其实可以不算
            if (currDepthCount < k) {
                k -= currDepthCount;
                continue;
            }
            // 说明存在这个分支之内，继续深度优先搜索
            hasSelected[i] = true;
            path = path + i;
            // 剪枝条件2，一次深度优先搜索到的结果肯定就是最后的结果....后面都不用算了
            return getPermutation2_DFS(n, k, depth + 1, path, hasSelected, facArray);
        }
    }
    return path;
};
// 计算阶乘方法
function getPermutation2_getFac(n: number): number[] {
    let facArray: number[] = [];
    facArray.push(1); // 0的阶乘是1
    for (let i = 1; i <= n; i++) {
        facArray[i] = facArray[i - 1] * i;
    }
    return facArray;
};



// 这道题目整体上来说是一道难度比较大的DFS相关的题目
// 首先有无重复全排列题目相关的经验在，首先最直观的想法就是使用深度优先搜索算法 + 回溯算法的思路
// 我们只需要依次计算全排列，然后当结果数组的长度 = 给定的k
// 然后后面的结果全部舍去不计算即可，但基于这种方案的时间复杂度其实并不理想，且需要耗费不少的空间

// 方法二则比方法一更加复杂，舍去回溯算法的部分，采用剪枝的策略进行，一次就算到最后相对应的结果
// 首先我们使用数学公式来计算阶乘数来辅助计算
// 在深度优先搜索的开始，我们设置一个depth变量来表示深度（实质上就是当前已经选择了多少个数字）
// 剪枝操作的部分主要包含：
// 1.每当我们选择一个数字之前，我们先计算假设选定了这个数字作为路径的开头，可以产生多少种组合
// 这个产生组合的过程就是通过阶乘数组来求出来的
// 计算出产生的组合后，若计算数小于k，说明即便加上了整个分支也达不到k，即这个分支其实可以不算
// 我们让k减去这个计算数之后，直接略去以这个数作为开头的路径选择过程，达到剪枝的效果
// 2. 因为在递归的过程中我们一直在不断的剪枝，即当路径满足结果要求的时候，这一定就是我们想要的结果
// （因为计算出它的时候k值一定等于当前的计算数且为0），所以只要算出了结果，后面的分支全部可以剪枝。